package org.example.Sort;

import org.example.Tool.Tool;

/**
 * <pre>
 * name 归并排序
 * time O(NLog^N)
 * space O(N)</pre>
 * */
public class MargeSort extends Tool {
    public void sort(int[] arr){
        if(Isfail(arr))return;//判断有效性
        System.out.println(process(arr, 0, arr.length - 1));
    }
    /**
     * 递归
     * */
    private int process(int[] arr, int L, int R){
        if(L==R){
            return 0;
        }
        int middle = L+((R-L)>>1);
        return process(arr,0,middle)   //排序左边数据
         + process(arr,middle+1,R)//排序右边数据
                + marge(arr,L,middle,R);  //合并
    }
    /**
     * 进行归并
     * */
    private int marge(int[] arr,int L,int M,int R){
        int p1=L;
        int p2=M+1;
        int[] temp = new int[R-L+1];
        int res = 0;
        int i =0;
        while(p1<=M&&p2<=R){  //首先双指针比较
            res += arr[p1]<arr[p2]?(R-p2+1)*arr[p1]:0;
            temp[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1<=M){//如果上述条件有一条不满足就算比较完了，填充剩下的数据；
            temp[i++] = arr[p1++];
        }
        while(p2<=R){
            temp[i++] = arr[p2++];
        }
        for (i = 0; i < temp.length; i++) {
            arr[L+i] = temp[i];
        }
        return res;

    }

}
